NP (klasa kompleksnosti)

U teoriji kompleksnosti, NP (nedeterminističko polinomijalno) je skup problema odluke, rješivih u polinomijalnom vremenu na nedeterminističkoj Turingovoj mašini. Ekvivalentno, to je skup problema čija rješenja mogu da se provjere na determinističkoj Turingovoj mašini u polinomijalnom vremenu.

NP se može smatrati kao skup problema odluke (odgovor 'da' ili 'ne') za koji se 'da'-rješenje u polinomijalnom vremenu može provjeriti sa determinističkom Turingovom mašinom. Problemi odluka za koje se 'ne'-rješenje jednostavno može kontrolisati, pripada Co-NP-u (komplement NP-a).

1. ^ Greška kod citiranja: Nevaljana oznaka <ref>; nije naveden tekst za reference s imenom Ladner